Assignment 1

Problem 1 unicode1

Python 字符串底层储存的是 Unicode 码点，但是在代码层来说很多字符难以进行直接输入，所以引入了一层转义。转义过程

• 正向：'\n' 到换行符，发生在字符串字面量进行解析时，即读取源代码期间就完成了转义，用户程序运行时是感知不到这一个过程的
• 逆向：换行符到 '\n'，发正在运行时调用 repr（为了人类可读性），字符串本身并不储存 '\' 和 'n'

以 chr(0) 为例，这是一个 str 对象，底层储存的码点序列仅包含为 0，这个对象直接作为 Python REPL 结果的话是 '\x00'，显示的结果等价于 print(repr(chr(0)))。不过，print 的输出和 REPL 回显本质上是不同的接口，他们的大体行为是一致的，即 expr 回显几乎等价于 print(repr(expr))，一个重要的例外是 None，RERP 回显的输出是空的。

Problem 2 unicode2

使用 UTF-8 的主要原因包括：节约内存，向后兼容 ASCII

错误的原因在于没有意识到 UTF-8 是变长编码，1-4 bytes 对应一个 char

2 byte 的序列只要不符合 110yyyyy 10xxxxxx 的格式或者对应的码点不在 Unicode 规范中就不构成一个合理的 Unicode char，第一点是容易构造的

Problem 3 train_bpe

把 data_text 按照 special_tokens 中的字符串拆成 no_spec_data_text_list: list[str]

实际上 special_tokens 之间的段并没有显式分开的需要，所以可以扁平化成一个 no_spec_data_text

然后用 PRETOKEN_PAT 模式来划分（regex.findall）no_spec_data_text，并按照 UTF-8 encoding 成 pretoken_data_bytes: list[bytes]。

merge 部分的思路

• 最朴素的想法：

  • 维护一个 pretoken_data_bytes_list: list[list[bytes]]，第一层是一个 pretoken，第二层是 pretoken 的 subword，初始全为单个 byte
  • 每一轮 merge：对所有 pretoken 按照 pairwise 遍历其 subwords 然后用 occurrence 记录相邻 subword 对出现的次数，维护 max_occur 和 max_pairs
  • 检查 max_pairs 是否非空，找到字典序最大的 max_pair，利用其维护 vocab、merges、token_cnt 以及 pretoken_data_byte_list 中所有 pretoken 的 subwords 数组
  • 显然复杂度爆炸了，每轮统计 occurence 和维护 pretoken_data_byte_list 都需要遍历整个数据集

• 增量更新：

  • 尝试对 occurence: dict[tuple[bytes, bytes], int] 做缓存，用直接更新 occurence 来替代更新 pretoken_data_byte_list 然后重新计算 occurence 的过程。每一轮更新，我们合并 max_pair[0] 和 max_pair[1] 这两个 subword，受到影响的 occurence 部分只有：对于某个 pretoken 的 subwords 中连续出现的 xxx max_pair[0] max_pair[1] yyy（xxx yyy 为空时下面的对应条目不存在），假设这样的形式有 pat_cnt 次，包括三种变化

    • occurence[(max_pair[0], max_pair[1])] 消失
    • occurence[(xxx, max_pair[0])] 减少 pat_cnt，occurence[(xxx, new_token)] 从零变为 pat_cnt（修正：增加 pat_cnt 因为可能有不同的 yyy）
    • occurence[(max_pair[1], yyy)] 减少 pat_cnt，occurence[(new_token, yyy)] 从零变为 pat_cnt（修正：增加 pat_cnt）
      于是我们需要
    • 一种能够快速找到所有这样的 xxx、yyy 的方法（并计算对应的 pat_cnt）。从而能够更新 occurence
    • 快速得到 occurence 中最大值以及所有满足条件的对应键的方法

  • 由于 subwords 出现顺序的信息是基于 pretoken 的，所以我们需要一个 occurence[(a, b)] 到所有具备这样的形式的 pretoken 的具体位置（因为一个 pretoken 可能匹配多次）的一个反向索引，我们不妨修改定义 occur: dict[tuple[bytes, bytes], list[tuple[int, int]] 其中类型 tuple[int, int] 对应 pretoken 在 pretoken_data_byte 中的索引以及 a b 的本次出现在 pretoken bytes 中的开始位置。（第二个索引是为了 pretoken 内计数）

    • 于是模式 xxx max_pair[0] max_pair[1] yyy 的所有出现必定是 occur[(max_pair[0], max_pair[1])] 的子集（修正：恰好为全集）。我们继续维护一个 pretoken 的 subwords 分割，然后遍历 occur[(max_pair[0], max_pair[1])]，在每个 pretoken 的分割的 max_pair 前 max_pair[1] 后的位置的 subword 就是 xxx 和 yyy（可能不存在）。至此我们得到了若干组 (xxx, yyy, pat_cnt)，然后更新 occur[(xxx, max_pair[0])] 等四个的值。
    • occur 本身的有序性（或者用一个新的数据结构来保存 occur 有序性）可以利用任意自平衡二叉树来维护，以 len(occur[(a, b)]) 作为键值（形式上来说）。occur 的维护过程对应一个删除，两个删除（以及两个插入），两个插入（修正：两个删除以及两个插入）。初始构造等价于遍历 pretoken_data_byte 按照 pairwise 再遍历所有 subword（初始对应单个字符）记录成字典 dict[tuple[int, int]] 然后统一插入。
    • 维护 pretoken 的 subwords 分割 subsplit: dict[int, list[tuple[bytes, int]]]，即某个 subword 在 pretoken 中出现的位置（bytes 意义上的），合并操作对应删除序列中的某两个元素替换为一个新元素（等价于删一个改一个），查询 xxx yyy 可以直接访问列表的前后元素。由于 pretoken 的长度一般不大所以直接用 list 似乎是可以接受的

  • 经过 Kimi K3 老师的开导

    • 相同 pair 的重叠出现时会出问题：
      a a a 合并 a a -> aa 按照上面的流程会导致更新第二个出现位置时这个出现位置在一个词内部。
      所以维护 subsplit 来解决 pretoken 内部索引不可行，因为重叠会导致这个 "出现位置索引" 失去意义。改为所有 pretoken 内部都动态地遍历更新（不采用上一轮计算的索引）（我们规定合并时优先合并左侧？），以此保证同一种 merge 中，后 merge 的出现位置能够感知到最新的变化。
      同时失去了 "出现位置索引" 之后我们不能再有 len(occur[(a, b)]) 来准确地判断模式出现的次数，并且 "我们看到的模式个数" 不等价于 "我们能改的模式个数"。我们规定我们维护 "能够看到的模式个数" 并以此作为有序性的来源。
      进行动态遍历更新之后，逐出现位置进行 occur 的维护会变麻烦
      我们改变更新 pretoken 内部每个出现位置的策略，遍历 occur[(sub1, sub2)]，对每个 (pre_grp, occur_pos) 在更新前检测 subsplit[pre_grp] 确保 subsplit 中有 (sub1, occur_pos) 和 (sub2, occur_pos + len(sub1))，如果存在那么执行更新，如果不存在进行删除。这么做的一个问题是
    • occur[(a, b)] 作为 list 其长度可以非常大，导致 occur 的维护（伴随有序性的元信息维护）的删除操作复杂度不可控，替换为 set
    • 另一个思路，不逐出现位置更新 occur，更新完某一个模式的所有出现位置之后统计一遍新的需要更新的 occur 部分然后整体增量更新

  • 最终流程：
    定义：
    occur: dict[tuple[bytes, bytes], set[tuple[int, int]]] 表示子词对 (sub1, sub2) 的所有出现 (pre_grp, occur_pos)
occur_cnts: st.SortedList[tuple[int, tuple[bytes, bytes]]] 按照 (occur_cnt, (sub1, sub2)) 自排序的数据结构。
    grp_split: dict[int, st.SortedDict[int, bytes]] 表示 pre_grp 的每一个出现 (occur_pos, bytes)。
    vocab: dict[int, bytes] 初始字符集合 + 每次合并产生的 subword，无需维护 token_cnt 用 len(vocab) 替代。
    merges: list[tuple[bytes, bytes]] 合并历史。
    初始：以 pairwise 遍历每个 pre_grp 统计所有相邻字符对来初始化 occur（所有相邻字符对）occur_cnts（所有相邻字符对的出现次数）grp_split（所有字符）
    循环：

    1. 取出找到 occur_cnts 中最大的元素 (occur_cnt, (subl, subr))，遍历 occur[(subl, subr)]，对于每个出现 (pre_grp, occur_pos)（如果标记删除则跳过）：
       • 根据 grp_split[pre_grp] 找到 (occur_pos, subl) 的相邻前驱 (subll_pos, subll) 和 (occur_pos + len(subl), subr) 的相邻后继 (subrr_pos, subrr)（二者军可能为空）。进行如下处理
       • 维护 grp_split[pre_grp]：删除 (occur_pos, subl) (occur_pos + len(subl), subr) 并添加 (occur_pos, new_sub)。
       • 维护 occur：
         • occur[(subll, subl)] 删除 (pre_grp, subll_pos)；
         • occur[(subr, subrr)] 删除 (pre_grp, occur_pos + len(subl))
         • occur[(subl, subr)] 删除 (pre_grp, occur_pos)。如果要删除的 pair 等于当前正在遍历的 (subl, subr) 则不能直接删，需要标记删除，等待遍历结束之后应用删除。
         • occur[(subll, new_token)] 添加 (pre_grp, subll_pos)。(subll, new_token) 不可能等于当前正在遍历的 (subl, subr)，直接操作
         • occur[(new_token, subrr)] 添加 (pre_grp, occur_pos)
         • 正义论
       • 维护 occur_cnts：
         • (cnt1, (subll, subl)) 变为 (cnt1 - 1, (subll, subl))；cnt - 1 归零则删除，cnt 原来不存在这初始为 0
         • (cnt2, (subl, subr)) 变为 (cnt2 - 1, (subl, subr))
         • (cnt3, (subr, subrr)) 变为 (cnt3 - 1, (subr, subrr))
         • (cnt4, (subll, new_token)) 变为 (cnt4 + 1, (subll, new_token))
         • (cnt5, (new_token, subrr)) 变为 (cnt5 + 1, (new_token, subrr))
    2. 维护 vocab 和 merges